/**
 * File : ThreeNumUtilss.java <br/>
 * Author : lenovo <br/>
 * Version : 1.1 <br/>
 * Date : 2017年1月2日 <br/>
 * Modify : <br/>
 * Package Name : com.MutiModule.common.codeing.twoSum <br/>
 * Project Name : MutiModule-common <br/>
 * Description : <br/>
 * 
 */

package com.MutiModule.common.codeing.twoSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName : ThreeNumUtilss <br/>
 * Function : 三个数字求和，和为某一个数. <br/>
 * Reason : 三个数字求和，和为某一个数 <br/>
 * Date : 2017年1月2日 下午1:42:05 <br/>
 * 
 * 首先是求解：因为要求3个数，如果我们固定其中1个数，再用求“和为某值的2个数的组合”的解法，就能把剩下的2个数求出来。因
	此，先对数组进行非递减排序，这样整个数组的数就由小到大排列。i 的取值由 0 至 n-1，对每一个i，我们求当num[i]是解当中的其
	中一个数时，其他的2个数。设有指针p指向数组头(实际只要p从i+1开始)，q指向数组尾，sum = num[i] + num[p]+ num[q]，因为num[i]
	是一定在解中的，所以如果sum < 0，因为num[q]已经不能增大，所以说明num[p]太小了，这时p需要向后移动，找一个更大的数。
	同理，sum > 0，说明num[q]太大了，需要q向前移动。当sum == 0时，说明找到了一个解。但找到了一个解，并不说明解中有num[i]的
	所有解都找到了，因此p或q还需要继续移动寻找其他的解，直到p == q为止。
 
	上面是求解的过程，那么去重怎么做？去重就在于和之前的解进行比较，但我们不需要比较所有的解，这里有一个技巧。
	1. 如果num[i] = num[i - 1]，说明刚才i-1时求的解在这次肯定也会求出一样的，所以直接跳过不求；
	2. 其实指针p不需要从数组头开始，因为如果num[i]所在的解中如果有i之前的数，设其位置为j，那么我们求num[j]时，肯定把num[i]
	    也找出来放到和num[j]一起的解里了，所以指针p其实应该从i+1开始，即初始时p = i + 1, q = num.size() - 1；
	3. 当sum == 0，我们保存了当前解以后，需要num[i]在解中的其他的2个数组合，这个时候，肯定是p往后或者q往前，如果++p，发
	    现其实num[p] == num[p-1]，说明这个解肯定和刚才重复了，再继续++p。同理，如果--q后发现num[q] == num[q+1]，继续--q。
	    这个去重操作主要针对这种有多个同值的数组，如：-3, 1,1,1, 2,2,3,4。
 * @author : alexgaoyh <br/>
 * @version : 1.1 <br/>
 * @since : JDK 1.6 <br/>
 * @see
 */

public class ThreeNumUtilss {

	/**
	 * 整体思想 三个数求和为某一个数，完全可以转换为两个数求和为某一个数。但是牵扯到去除重复结果集的问题，则可以优先对数组进行排序，如果
	 * 前后两个值相同，则前一个值的结果跟这个值的结果是一样的。
	 * 	
	 *  功能：<br/>
	 *
	 * @author alexgaoyh
	 * @version 2017年1月2日 下午1:42:52 <br/>
	 */
	public static void main(String[] args) {
		int[] nums = new int[]{-1,0,1,1,-2,2};
		List<List<Integer>> returnList = threeSum(nums);
		System.out.println(returnList);
	}

	/**
	 * 数组需要优先排序，这样求解出来一个值之后，往前往后的值如果跟其中一个值一样，那么这个值求解出来的结果也是一样的，所以需要增加/减少多次；
	 * 功能：<br/>
	 *
	 * @author alexgaoyh
	 * @version 2017年1月2日 下午2:05:39 <br/>
	 */
	public static List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> ans = new ArrayList<List<Integer>>();
		int length = nums.length;
		if (nums == null || length < 3)
			return ans;
		Arrays.sort(nums);
		for (int i = 0; i < length - 2; ++i) {
			// 当前值和之前的值一样，那么求解出来的结果也是一样的，可以直接跳过处理
			if (i > 0 && nums[i] == nums[i - 1])
				continue;
			findTwoSum(ans, nums, i + 1, length - 1, nums[i]);
		}
		return ans;
	}

	public static void findTwoSum(List<List<Integer>> ans, int[] num, int begin, int end, int target) {
		// 需要求解出来所有的值，那么首尾指针需要碰面才算结束
		while (begin < end) {
			if (num[begin] + num[end] + target == 0) {
				List<Integer> list = new ArrayList<Integer>();
				list.add(target);
				list.add(num[begin]);
				list.add(num[end]);
				ans.add(list);
				while (begin < end && num[begin + 1] == num[begin])
					begin++;
				begin++;
				while (begin < end && num[end - 1] == num[end])
					end--;
				end--;
			}else if (num[begin] + num[end] + target > 0)
				end--;
			else
				begin++;
		}
	}
}
